One objective of compilation systems for quantum computing is the decomposition of any required single-qubit unitary operation into sets of gates that can implement arbitrary single-qubit unitary operations. Typically, gate sets that provide fault tolerance are preferred. One gate set that has been identified is referred to as the {H,T} gate set that includes the Hadamard gate and the T-gate. This gate set is universal for single-qubit unitaries (can realize arbitrary single-qubit unitary operations to required precision) and is fault tolerant.
The {H,T} gate set has been used to implement circuits, but historically resulting circuits had excessive cost. Significant progress has been made in the last two years in reducing the cost, but there is ample room for improvement. It has been shown that adding ancillary qubit(s), a two-qubit gate (for example, CNOT or CZ), and measurement operations to the gate set can result in lower cost computation. One approach is based on so-called Repeat-Until-Success (RUS) circuits in which an intended output state can be identified using a measurement of an ancillary qubit and a sequence of Clifford+T gates, where the Clifford+T gate set includes the two-qubit CNOT gate (or CZ gate), the Hadamard gate, and the T-gate. Paetznick and Svore, “Repeat-Until-Success: Non-deterministic decomposition of single-qubit unitaries,” available at http://arxiv.org/abs/1311.1074, describe methods for implementing rotations using the Clifford+T gates in combination with measurements and classical feedback. The RUS method achieves superior computation cost. However, these methods are based on an exhaustive search and require exponential runtime. Thus, these methods are limited in achievable precision and hence in applicability.